﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace CSharpAlgorithm.Base
{
    /// <summary>
    /// 디닉 플로우 알고리즘
    /// O(E * V^2)
    /// </summary>
    class Dinic
    {
        private List<Edge>[] G;
        private int maxSize;
        private int[] level; //s로 부터의 거리
        private int[] iter; //어디까지 조사해야 하나
        public Dinic(int maxSize)
        {
            this.maxSize = maxSize;
            G = new List<Edge>[maxSize];
            for (int i = 0; i < G.Length; i++)
            {
                G[i] = new List<Edge>();
            }
        }
        public void AddEdge(int from, int to, int cap)
        {
            G[from].Add(new Edge(0, to, 0, cap, G[to].Count));
            G[to].Add(new Edge(0, from, 0, 0, G[from].Count - 1));
        }
        private void Bfs(int s)
        {
            level = new int[maxSize + 1];
            for (int i = 0; i < level.Length; i++)
            {
                level[i] = -1;
            }
            
            Queue<int> que = new Queue<int>();
            level[s] = 0;
            que.Enqueue(s);
            while (que.Count > 0)
            {
                int v = que.Dequeue();
                for (int i = 0; i < G[v].Count; i++)
                {
                    Edge e = G[v][i];
                    if (e.Cap > 0 && level[e.To] < 0)
                    {
                        level[e.To] = level[v] + 1;
                        que.Enqueue(e.To);
                    }
                }
            }
        }
        private int Dfs(int v, int t, int f)
        {
            if (v == t) return f;
            for (int i = iter[v]; i < G[v].Count; i++)
            {
                Edge e = G[v][i];
                if (e.Cap > 0 && level[v] < level[e.To])
                {
                    int d = Dfs(e.To, t, Math.Min(f, e.Cap));
                    if (d > 0)
                    {
                        e.Cap -= d;
                        Edge g = G[e.To][e.Rev];
                        g.Cap += d;
                        return d;
                    }
                }
            }
            return 0;
        }
        public int MaxFlow(int s, int t)
        {
            int flow = 0;
            for (; ; )
            {
                Bfs(s);
                if (level[t] < 0) return flow;
                iter = new int[maxSize + 1];
                int f;
                while ((f = Dfs(s, t, Int32.MaxValue)) > 0)
                {
                    flow += f;
                }
            }
        }
    }
}
